package leetcode_day._2021._202112._2131;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/30 9:18
 * 一手顺子
 * 算法：哈希表 + 优先队列
 * 使用哈希表来记录每个数字的个数
 * 用优先队列来存储数组，每次取出第一个数（也就是最小的数）来遍历
 */
public class _30_846 {

    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) return false;
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a));
        Map<Integer, Integer> map = new HashMap<>(16);
        for (int i : hand) {
            queue.offer(i);
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        while (!queue.isEmpty()) {
            final Integer poll = queue.poll();
            if (map.getOrDefault(poll, 0) <= 0) continue;
            for (int i = 0; i < groupSize; i++) {
                int cur = poll + i, cnt = map.getOrDefault(cur, 0);
                if (cnt > 0) map.put(cur, cnt - 1);
                else return false;
            }
        }
        return true;
    }

}
